package datastructure.book.dp._1_pathway.exercise.first;

import org.junit.jupiter.api.Test;

public class _6_Solution {
    /**
     * 给你一个n x n 整数矩阵grid，请你返回 非零偏移下降路径 数字和的最小值。
     * 非零偏移下降路径 定义为：从grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，
     * 相邻数字不在原数组的同一列。
     * n == grid.length == grid[i].length
     * 1 <= n <= 200
     * -99 <= grid[i][j] <= 99
     * 例如：grid = [
     * [1,2,3],
     * [4,5,6],
     * [7,8,9]]
     * 所有非零偏移下降路径包括：
     * [1,5,9], [1,5,7], [1,6,7], [1,6,8],
     * [2,4,8], [2,4,9], [2,6,7], [2,6,8],
     * [3,4,8], [3,4,9], [3,5,7], [3,5,9]
     * 下降路径中数字和最小的是[1,5,7] ，所以答案是13 。
     */
    public int minFallingPathSum(int[][] grid) {
        if (grid.length == 1) {
            return grid[0][0];
        }
        int minIndex = 0;
        int minValue = grid[0][0];
        Integer secValue = null;
        for (int i = 1; i < grid.length; i++) {
            int value = grid[0][i];
            if (value < minValue) {
                secValue = minValue;
                minValue = value;
                minIndex = i;
            } else if (secValue == null || value < secValue) {
                secValue = value;
            }
        }
        for (int i = 1; i < grid.length; i++) {
            int tempMinIndex = minIndex;
            int tempMinValue = secValue+grid[i][tempMinIndex];
            Integer tempSecValue = null;
            for (int j = 0; j < minIndex; j++) {
                int value = grid[i][j]+minValue;
                if (value < tempMinValue) {
                    tempSecValue = tempMinValue;
                    tempMinValue = value;
                    tempMinIndex = j;
                } else if (tempSecValue == null || value < tempSecValue) {
                    tempSecValue = value;
                }
            }
            for (int j = minIndex+1; j < grid.length; j++) {
                int value = grid[i][j]+minValue;
                if (value < tempMinValue) {
                    tempSecValue = tempMinValue;
                    tempMinValue = value;
                    tempMinIndex = j;
                } else if (tempSecValue == null || value < tempSecValue) {
                    tempSecValue = value;
                }
            }
            minValue = tempMinValue;
            minIndex = tempMinIndex;
            secValue = tempSecValue;
        }
        return minValue;
    }

    @Test
    public void test(){
        //正确结果：-807
        int[][] num = new int[][]{
                {50,-18,-38,39,-20,-37,-61,72,22,79},
                {82,26,30,-96,-1,28,87,94,34,-89},
                {55,-50,20,76,-50,59,-58,85,83,-83},
                {39,65,-68,89,-62,-53,74,2,-70,-90},
                {1,57,-70,83,-91,-32,-13,49,-11,58},
                {-55,83,60,-12,-90,-37,-36,-27,-19,-6},
                {76,-53,78,90,70,62,-81,-94,-32,-57},
                {-32,-85,81,25,80,90,-24,10,27,-55},
                {39,54,39,34,-45,17,-2,-61,-81,85},
                {-77,65,76,92,21,68,78,-13,39,22}
        };
//        num = new int[][]{
//                {1,2,3},
//                {4,5,6},
//                {7,8,9}
//        };
        System.out.println(minFallingPathSum(num));
    }
}
